package cn.edu.njust.alg;

public class LCS {

	public static int lcs(String s1, String s2) {

		int[][] arr = new int[s1.length()+1][s2.length()+1];
		for(int i=0;i<s1.length();i++){
			
			for(int j=0;j<s2.length();j++){
				if(s1.charAt(i)==s2.charAt(j)){
					arr[i+1][j+1] =arr[i][j]+1;
				}else{
					arr[i+1][j+1]=Math.max(arr[i][j+1], arr[i+1][j]);
				}
			}
		}
		return arr[s1.length()][s2.length()];
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s1 = "abcdefg";
		String s2 = "aeb";
		System.out.println(lcs(s1,s2));
	}

}
